This relates to multi-dimension connection networks. It is particularly useful in the interconnection of parallel processors such as those described in the abovereferenced U.S. Pat. No. 4,598,400 and will be described in that context, but it has applications in other areas as well.
As shown in FIG. 1A of U.S. Pat. No. 4,598,400, the parallel processor system of that patent comprises a mainframe computer 10, a microcontroller 20, an array 30 of parallel processing integrated circuits 35, a data source 40, a first buffer and multiplexer/demultiplexer 50, first, second, third and fourth bidirectional bus control circuits 60, 65, 70, 75, a second buffer and multiplexer/demultiplexer 80, and a data sink 90. Mainframe computer 10 may be a suitably programmed commercially available general purpose computer such as a VAX computer manufactured by Digital Equipment Corp. Microcontroller 20 is an instruction sequencer of conventional design for generating a sequence of instructions that are applied to array 30 by means of a thirty-two bit parallel bus 22. Microcontroller 20 receives from array 30 a signal on line 26. Bus 22 and line 26 are connected in parallel to each IC 35. As a result, signals from microcontroller 20 are applied simultaneously to each IC 35 in array 30 and the signal applied to microcontroller 20 on line 26 is formed by combining the signal outputs from all of ICs 35 of the array.
Array 30 contains thousands of identical ICs 35; and each IC 35 contains several identical processor/memories 36. In the embodiment disclosed in the '400 patent, it is indicated that the array may contain up to 32,768 (=2.sup.15) identical ICs 35; and each IC 35 may contain 32 (=2.sup.5) identical processor/memories 36. At the time of filing of this application for patent, arrays containing up to 4096 (=2.sup.12) identical ICs 35 containing 16 (=2.sup.4) identical processor/memories each have been manufactured and shipped by the assignee as Connection Machine (Reg. TM) computers.
The '400 patent discloses a parallel processor in which processor/memories 36 are organized and interconnected in two geometries. The first is a conventional two-dimensional grid pattern in which the processor/memories are organized in a square array and connected to their four nearest neighbors in the array. The second is a Boolean n-cube of fifteen dimensions. To connect processor/memories 36 in a two-dimensional grid pattern, ICs 35 of array 30 are organized in a rectangular array of 256 (=2.sup.8) rows and 128 (=2.sup.7) columns; and the 32 processor/memories of each IC are connected in a rectangular array of 4 (=2.sup.2) rows and 8 (=2.sup.3) columns. As a result, the 1,048,576 processor/memories 36 of array 30 are connected in a square of 1024 (=2.sup.10) rows and 1024 columns. For convenience, the sides of this square array are identified as NORTH, EAST, SOUTH and WEST. To connect each processor/memory to its four nearest neighbors, the individual processor/memories are connected by electrical conductors between adjacent processor/memories in each row and each column; and the four nearest neighbors of any IC except those on the edges of the array will be recognized to be the four ICs immediately adjacent that IC on the North, East, South and West, respectively.
The above-described two dimensional grid does not provide for rapid interchange of data in random directions between processor/memories 36 in the two-dimensional array. Moreover, to move data between an edge of the array and a specific processor/memory, it is necessary to shift it through all the processor/memories between the edge and the processor/memory of interest, which may require shifts through more than 500 processor/memories. Even where it is possible to make a single such shift at very high speeds, the need to do more than 500 such shifts makes the complete operation maddeningly slow. With the added complications of making such shifts at the same time for large numbers of processor/memories in random and independent directions, it becomes impossible to operate such a large two-dimensional grid of processor/memories at reasonable cost.
This problem is alleviated by also organizing and interconnecting processor/memories 36 in accordance with a second geometry. In particular, in the example set forth in the '400 patent, ICs 35 are organized and interconnected in the form of a Boolean n-cube of fifteen dimensions. Each IC is provided with logic circuitry to control the routing of messages through such an interconnection network; and within each IC, bus connections are provided to the thirty-two processor/memories so that every one of the more than one million processor/memories can send a message to every other. Moreover, large numbers of messages may be sent at any time and the messages may be routed in random directions.
The advantages of such hyper-dimensional interconnection network are so substantial compared with those of the conventional two-dimensional interconnection network that the question arises whether two interconnection networks can be justified. The two-dimensional network has the advantage that it is identical in structure to many data arrays that might be manipulated by parallel processors. Thus, with a two-dimensional interconnection network it is possible to perform quite readily operations on left or right, upper or lower neighbors such as are often performed in manipulating two-dimensional data arrays. However, the cost of the two-dimensional network is a large amount of the limited area on an integrated circuit and a very high number of the interconnections or pins on the integrated circuit relative to the function provided. For example, if each integrated circuit carries a 4.times.4 array of processors, then 16 pins are needed to provide for connections to left and right, upper and lower neighboring processors on adjacent integrated circuits. While these numbers can be reduced by multiplexing the pin directions, a minimum of three pins are still needed for this size array.